# 动态规划50题 https://www.bilibili.com/video/BV1aa411f7uT
# 1/50 爬楼梯
# leetcode第70题: https://leetcode.cn/problems/climbing-stairs/description/

def climbStairs(n: int) -> int:
    dp = [1, 1]
    for i in range(2, n + 1):
        dp.append(dp[i - 1] + dp[i - 2])
    return dp[n]


print(climbStairs(3))
